package arithmetic;

import java.util.*;

public class StackTest {
    public static void main(String[] args) {
       int[]  a = {73,74,75,71,69,72,76,73};
        int[] ints = dailyTemperatures(a);
        System.out.println(ints);
    }

    public static int[] dailyTemperatures(int[] temperatures) {
        //定义一个单调栈，对每个元素入栈，当下一个元素大于当前元素的时候，弹出当前元素，继续比较，直到小于当前元素。
        //单调栈里面存的是当前温度和下标值[当前温度,下标]
        Stack<int[]> stack = new Stack<>();
        int[] result = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            //当前温度
            int temperature = temperatures[i];
            //判断当前温度是否大于栈内温度
            while (!stack.isEmpty() && temperature > stack.peek()[0]) {
                //大于，出栈，并且存入result当前下标和出栈下标的差值
                int[] node = stack.pop();
                result[node[1]] = i - node[1];
            }
            //小于，入栈，存入温度和索引
            int[] node = {temperature,i};
            stack.push(node);
        }
        //stack里面剩下的是单调递减数组,直接存入0
        while (!stack.isEmpty()) {
            int[] node = stack.pop();
            int i = node[1];
            result[i]=0;
        }
        return result;
    }


}